#pragma once

#include <iostream>

using std::cout;
using std::endl;

class SkipList{
private:
    struct Node{
        Node(int val = int())
            : val(val)
            , next(nullptr)
            , down(nullptr)
        {}
        int val;
        Node *next;
        Node *down;
    };

    struct HeadNode: Node{
        HeadNode(int l)
            : level(l)
        {}
        int level;
    };

private:
    HeadNode *head_;

public:

    SkipList()
    {
        head_ = new HeadNode(1);
        srand(time(nullptr));
    }

    ~SkipList()
    {
        HeadNode *pre = head_;
        Node *cur = pre->next;
        while(pre){
            Node *tmp = cur;
            while(cur){
                tmp = cur;
                cur = cur->next;
                delete tmp;
            }
            tmp = pre;
            if(pre->down)
                pre = static_cast<HeadNode *>(pre->down);
            else
                pre = nullptr;
            delete tmp;
        }
    }

    int getLevel() const
    {
        int level = 1;
        while((rand() % 100 < 50) && (level < head_->level + 1)){
            level++;
        }

        return level;
    }

public:
   bool find(int val)
    {
        Node *pre = head_;
        Node *cur = pre->next;

        while(pre){
            if(cur){
                if(cur->val < val){
                    pre = cur;
                    cur = cur->next;
                    continue;
                }else if(cur->val == val){
                    return true;
                }
            }

            if(!cur || cur->val > val){
                pre = pre->down;
                if(pre)
                    cur = pre->next;
            }
        }

        return false;
    }

    void add(int val)
    {
        // 不能存储重复值，如果有当前值，直接返回
        if(find(val))
            return;
        
        int level = getLevel();
        if(level > head_->level){
            HeadNode *hnode = new HeadNode(level);
            hnode->down = head_;
            head_ = hnode;
        }

        // 首先创建要添加的节点，让上面的节点指向下面的节点
        Node **nodes = new Node*[level];
        for(int i{level - 1}; i >= 0; i--){
            nodes[i] = new Node(val);
            if(i < level - 1){
                nodes[i]->down = nodes[i + 1];
            }
        }
        Node *insertNode = nodes[0];
        delete [] nodes;

        // 找到要插入的层
        HeadNode *hnode = head_;
        for(int i{hnode->level}; i != level; i--){
            hnode = static_cast<HeadNode *>(hnode->down); 
        }

        Node *pre = hnode;
        Node *cur = pre->next;
        // DEBUG
        // static int i = 0;
        // printf("i=%d, cur-level = %d, insert level = %d\n", ++i, head_->level, level);

        while(pre){
            if(cur){
                if(cur->val < val){
                    pre = cur;
                    cur = cur->next;
                }
            }
            if(!cur || cur->val > val){
                insertNode->next = cur;
                pre->next = insertNode;
                insertNode = insertNode->down;

                pre = pre->down;
                if(pre)
                    cur = pre->next;
            }
        }

    }

    void erase(int val)
    {
        Node *pre = head_;
        Node *cur = pre->next;
        while(pre){
            if(cur){
                if(cur->val < val){
                    pre = cur;
                    cur = cur->next;
                    continue;
                }else if(cur->val == val){
                    pre->next = cur->next;
                    delete cur;
                    if(pre == head_ && !pre->next){
                        head_ = static_cast<HeadNode *>(head_);
                        delete pre;
                        pre = head_;
                    }
                    
                    pre = pre->down;
                    if(pre)
                        cur = pre->next;
                }
            }

            if(pre){
                if(!cur || cur->val > val){
                    pre = pre->down;
                    if(pre) 
                        cur = pre->next;
                }
            }

        }
    }

    void show()
    {
        Node *pre = head_;
        while(pre){
            Node *cur = pre->next;
            while(cur){
                cout << cur->val << " ";
                cur = cur->next;
            }
            cout << endl;
            pre = pre->down;
        }
    }

};